An adjustment-value-attached block cipher is a block cipher having adjustment values referred to as tweak, in addition to plaintext, ciphertext and a key, which are input/output that an ordinary block cipher has.
In an adjustment-value-attached block cipher, it is required that the outputs (ciphertexts) of two block ciphers having different adjustment values appear to be random values independent from each other for an attacker who already knows the adjustment values and an input (plaintext). When such a characteristic is provided, the adjustment-value-attached block cipher can be said to be secure.
Some block ciphers having auxiliary inputs similar to tweak have been proposed. In the ciphers, however, strict requirements for safety and the like are not defined.
A formal definition of an adjustment-value-attached block cipher was made in Non-patent Document 1 first.
In Non-patent Document 1, it was also shown that a theoretically safe adjustment-value-attached block cipher can be obtained as an operation mode (hereinafter abbreviated as “mode”) of an ordinary block cipher, that is, obtained as conversion using the block cipher as a black box.
The theoretically safety stated here means that the safety of an adjustment-value-attached block cipher obtained as a mode of a certain block cipher can be attributed to the safety of the original block cipher, that is, means that, as long as safe block cipher is used, an adjustment-value-attached block cipher obtained as a mode of the block cipher is also safe.
There are two kinds of definitions of safety: safety in the case where an attacker can execute only a chosen-plaintext attack (CPA), and safety in the case where an attacker can execute a combination of the chosen-plaintext attack and a chosen-ciphertext attack (CCA). The former is referred to as CPA-security, and the latter is CCA-security.
A safe adjustment-value-attached block cipher is known to be a key technique for realizing a high-level encryption function.
For example, it is pointed out in Non-patent Document 2 that very efficient authentication-function-provided encryption can be realized by using an adjustment-value-attached block cipher having CCA-security, and that an efficient parallel-executable message authentication code can be realized by using an adjustment-value-attached block cipher having CPA-security.
Furthermore, the adjustment-value-attached block cipher having CCA-security is known to be a technique essential for storage encryption such as disk sector encryption.
Here, the mode proposed in Non-patent Document 1 will be referred to as an LRW mode.
FIG. 1 is a block diagram for illustrating encryption processing in the LRW mode, specifically, encryption processing using n-bit block cipher (hereinafter, simply referred to as “block cipher”) E in the LRW mode.
In the LRW mode, a multiplication section 11M implemented with a function mul for performing multiplication on a finite field GF(2n) is required in addition to the encryption section 11E implemented with the block cipher E. Here, mul(x, y) indicates a result of multiplication of x and y, which are two elements on finite field GF(2n). In the LRW mode, one of the arguments of the function mul is an n-bit uniform random number K2. The uniform random number K2 is a key independent from a key K1 of the block cipher E. Another argument of the function mul is tweak.
In the LRW mode, the function mul creates a value to be added to plaintext provided for block cipher E and a value to be added to ciphertext generated by block cipher E. Such a function (the function mul in this case) will be referred to as an “offset function”, and output of the offset function will be referred to as offset.
More generally, the offset function is not limited to the function mul. It may be such a function F in which an independent key and tweak are arguments.
Here, the function F is required to have a characteristic that, when a security parameter is denoted by e (e is 0 or more and 1 or less), Pr[f(K, x)+f(K, x′)=c] is e or less for any c, x and x′ (where x and x′ differ). Here, “+” indicates exclusive-OR.
When the function F has this characteristic, f(K, *) is said to be e-almost XOR universal (e-AXU). The e-AXU function is a kind of universal hash function. The function mul is ½n-AXU.
The e-AXU function can be realized not only by the function mul but also by a system proposed in Non-patent Document 3.
The speed of these e-AXU functions is several times higher than a general block cipher in a particular implementation environment.
However, such an e-AXU function that can be implemented in any computer environment and that is faster than block cipher is not known.
Therefore, it is a problem that the e-AXU function is not effective unless it is in an environment where it can be implemented at a high speed. Furthermore, it is also a problem that the program size is generally larger in comparison with the case of implementing only block cipher E, because two parts of block cipher E and the e-AXU function (for example, the function mul) are implemented.
On the other hand, the XEX mode described in Non-patent Document 2 is known as an adjustment-value-attached block cipher which uses only the block cipher E.
FIG. 2A is a block diagram for illustrating the XEX mode.
In FIG. 2A, tweak is divided into two parts. That is, it is expressed as tweak=(tweak1, tweak2). An offset function pow performs multiplication of encrypted tweak1 E (K1, tweak1) and btweak2 where a certain radix is denoted by b and tweak2 is an index. That is, offset is indicated by the following [Expression pow].pow(tweak2, E(K1, tweak1))=mul(btweak2, E(K1, tweak1))  [Expression pow]
If multiple radixes exist when the function pow is determined, tweak2 may be a combination of the indexes of the radixes (for example, if the radixes are b1 and b2, then tweak2=(tweak21, tweak22)). A first argument of the function pow in this case is the product of b1tweak21 and b2tweak22, that is, mul(b1tweak21, b2tweak22).
In any of the cases, there is an advantage that, by appropriately selecting a radix, it is possible to calculate an offset only by one bit shift and one exclusive-OR of constants when tweak2 is incremented, that is, when only the addition of 1 to the value of tweak2 immediately before is performed. In other words, calculation of an offset can be executed in an extremely short time, in comparison with encryption of a block cipher.
However, since tweak2 at a certain time point can be only such that is obtained by incrementing tweak2 immediately before, the XEX mode is not suitable for application in which tweak2 arbitrarily changes.
In the XEX mode shown in FIG. 2A, it is possible to perform an arbitrary update of tweak formally by fixing tweak2 to a constant and handling only tweak1 as tweak. However, this causes the length of tweak to be shortened. Furthermore, calculation of an offset requires the amount of calculation that is required for encryption of one block. Therefore, in the XEX mode in this case, two block cipher calls are required for encryption of one block message.
Both the LRW mode and the XEX mode have CCA-security. However, if the second exclusive-OR by offset is omitted in the LRW mode and XEX mode, the obtained mode is a mode having only CPA-security.
From the viewpoint of the concept of safety, CPA-security is weaker than CCA-security. However, it is known that CPA-security is satisfactory for some purposes such as message authentication.
In Non-patent Document 2, such a mode in which the exclusive-OR of ciphertext generated by the block cipher E and offset is omitted in the XEX mode is defined as an XE mode. FIG. 2B is a block diagram showing encryption processing in the XE mode.
Furthermore, in Non-patent Document 2, an XEX* mode in which the XE mode and the XEX mode coexist is proposed. The XEX* mode is such a mode that a user can specify which of the XE mode and the XEX mode processing is to be performed, for each tweak. FIG. 2C is a block diagram showing encryption processing in the XEX* mode.
In the XEX* mode, however, when processing is performed for a certain tweak in the XE mode, processing in the XEX mode cannot be performed with the same tweak. On the contrary, when processing is performed for a certain tweak in the XEX mode, processing in the XE mode cannot be performed with the same tweak, either.
One-bit information specifying which of the XE mode and the XEX mode is to be used is referred to as a tag “tag”. A mode which a user uses by specifying a tag and tweak as described above will be also referred to as adjustment-value-attached block cipher here.
An advantage of the XEX* mode is that, in the case where CPA-security is required for processing with a certain tweak but in which CCA-security is required for processing with another tweak, the efficiency is improved in comparison with the case of simply using the XEX mode. That is, by using not the XEX mode but the XE mode in processing with a tweak for which CPA-security is required, an exclusive-OR operation of offset on the ciphertext side can be omitted.
In the XEX* mode, however, the exclusive-OR operation on the plaintext side cannot be omitted in any of the processing operations as long as the XE mode is used. Specifically, the XEX* mode is used for OCB2.0 which is an authentication-function-provided encryption mode described in Non-patent Document 4. This is an improvement of OCB described in Patent Document 1.    Patent Document 1
Specification of U.S. Pat. No. 7,046,802    Non-Patent Document 1
Moses Liskov, Ronald L. Rivest, David Wagner: Tweakable Block Ciphers. Advances in Cryptology—CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, Calif., USA, Aug. 18-22, 2002, Proceedings. Lecture Notes in Computer Science 2442 Springer 2002, pp. 31-46    Non-Patent Document 2
P. Rogaway: Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC. Advances in Cryptology—ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, Dec. 5-9, 2004, Proceedings. Lecture Notes in Computer Science 3329 Springer 2004, pp. 16-31    Non-Patent Document 3
S. Halevi and H. Krawczyk, MMH: Software Message Authentication in the Gbit/second rates, Fast Software Encryption, 4th International Workshop, FSE '97, Lecture Notes in Computer Science; Vol. 1267, February 1997    Non-Patent Document 4
T. Krovetz and P. Rogaway. The OCB Authenticated-Encryption Algorithm. Internet draft, March 2005    Non-patent Document 5 J. Daemen and V. Rijmen, AES Proposal: Rijndael, AES submission, 1998. http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael.pdf    Non-Patent Document 6
S. Park, S. H. Sung, S. Lee, and J. Lim, Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structure and AES, International Workshop, FSE 2003, Lecture Notes in Computer Science; Vol. 2887, February 2003